151. 反转字符串中的单词
151. 反转字符串中的单词
分析
其实这个题的思路很简单，先移除多余空格，然后反转整个字符串，再反转单词对应的字符串。
反转整个字符串这一步我们就不说了，跟 344. 反转字符串 一模一样，移除多余空格和反转字符串中的单词写起来还是有一点难度的
移除空格
移除空格部分的代码跟 27. 移除元素 的方法其实是一样的，就是双指针法。
常规的方法是先移除头部的空格，再移除尾部的空格，最后移除中间部分的空格，去除中间空格的时候，首先判断当前 fast 指针指向的字符，是不是空格，如果不是，则说明是目标字符，同时移动快慢指针，如果是，则查看上一个确定的字符（slow 指向的字符）是不是空格，如果不是，则也是目标字符，同时移动快慢指针，如果是，说明当前是连续空格字符，不是目标字符。
// 移除空格
public String removeSpace(char[] chars){
// 还是用双指针法
int left = 0, right = chars.length-1;
// 移除头部的空格
while(chars[left]==' '){
left++;
}
// 移除尾部的空格
while(chars[right]==' '){
right--;
}
// 此时 left 和 right 指向的都是不为空格的字符
// slow 指的是下一个要插入的位置
int slow =left+1;
// fast 指向的是下一个需要检查的位置
int fast =left+1;
while(fast<=right){
// 如何移除中间的空格呢？
// 如果当前遍历字符不是空格，则同时移动快慢指针，
// 如果当前遍历字符是空格，而且上一个确定的字符不是空格，则同时移动快慢指针，
// 如果当前遍历字符是空格，而且上一个确定的字符也是空格，则仅移动快指针，即跳过此字符。
if(chars[fast]!=' '||chars[slow-1]!=' '){
chars[slow]=chars[fast];
slow++;
fast++;
}else{
fast++;
}
}
// 此时slow指的是下一个位置的索引，copyOfRange的第三个参数指向的索引刚好是排除的。
return new String(Arrays.copyOfRange(chars, left, slow));
}
其实也可以不用分三步，可以一步到位，但是比较难想
public String removeSpace(char[] chars){
int slow = 0, fast = 0;
while (fast < chars.length) {
// 如果当前字符是空格，而且
// 这是第一个字符或是最后一个字符，那肯定都是跳过
// 这个 ' ' == chars[fast + 1] 是为了处理末尾连续多个空格
if(' ' == chars[fast] && (fast == 0 || fast==chars.length-1 || ' ' == chars[fast + 1] || slow == 0 || ' ' == chars[slow - 1])){
fast++;
}else{
chars[slow] = chars[fast];
fast++;
slow++;
}
}
// 此时slow指的是下一个位置的索引，copyOfRange的第三个参数指向的索引刚好是排除的。
return new String(Arrays.copyOfRange(chars, 0, slow));
}
反转单词
反转单词最终的是找到单词的起点和重点，
如果上一个字符没有或者上一个字符是空格，那么当前就是单词的起点
如果当前字符不为空格，但是是字符串的末尾，或者不是末尾且下一个字符是空格，那么当前就是单词的末尾
public String reverseWordInStr(char[] chars) {
char lastChar = 0;
int wordStart = 0, wordEnd = 0;
for (int i = 0; i < chars.length; i++) {
// 如果lastChar不存在或者lastChar是空格，当前就是单词的起点
if ((lastChar == 0 || ' ' == lastChar)) {
wordStart = i;
}
// 如果当前不是空格，下一个是空格，或者当前就是字符串的末尾了
if (' ' != chars[i] && (i == chars.length - 1 || ' ' == chars[i + 1])) {
wordEnd = i;
// 开始反转
for (; wordStart < wordEnd;) {
char temp = chars[wordStart];
chars[wordStart] = chars[wordEnd];
chars[wordEnd] = temp;
wordStart++;
wordEnd--;
}
wordStart = 0;
wordEnd = 0;
}
lastChar = chars[i];
}
return new String(chars);
}
解题
class Solution {
public String reverseWords(String s) {
// 反转两次即可
// 先把整个字符串反转，然后再把单词反转
char[] chars = s.toCharArray();
String cleanStr = removeSpace(chars);
chars = cleanStr.toCharArray();
int left = 0, right = chars.length - 1;
for (; left < right;) {
char temp = chars[left];
chars[left] = chars[right];
chars[right] = temp;
left++;
right--;
}
// 开始反转单词
return reverseWordInStr(chars);
}
public String removeSpace(char[] chars) {
// 还是用双指针法
int left = 0, right = chars.length - 1;
// 移除头部的空格
while (chars[left] == ' ') {
left++;
}
// 移除尾部的空格
while (chars[right] == ' ') {
right--;
}
// 此时 left 和 right 指向的都是不为空格的字符
// slow 指的是下一个要插入的位置
int slow = left + 1;
// fast 指向的是下一个需要检查的位置
int fast = left + 1;
while (fast <= right) {
// 如何移除中间的空格呢？
// 如果当前遍历字符不是空格，则同时移动快慢指针，
// 如果当前遍历字符是空格，而且上一个确定的字符不是空格，则同时移动快慢指针，
// 如果当前遍历字符是空格，而且上一个确定的字符也是空格，则仅移动快指针，即跳过此字符。
if (chars[fast] != ' ' || chars[slow - 1] != ' ') {
chars[slow] = chars[fast];
slow++;
fast++;
} else {
fast++;
}
}
// 此时slow指的是下一个位置的索引，copyOfRange的第三个参数指向的索引刚好是排除的。
return new String(Arrays.copyOfRange(chars, left, slow));
}
public String reverseWordInStr(char[] chars) {
char lastChar = 0;
int wordStart = 0, wordEnd = 0;
for (int i = 0; i < chars.length; i++) {
// 如果lastChar不存在或者lastChar是空格，当前就是单词的起点
if ((lastChar == 0 || ' ' == lastChar)) {
wordStart = i;
}
// 如果当前不是空格，下一个是空格，或者当前就是字符串的末尾了
if (' ' != chars[i] && (i == chars.length - 1 || ' ' == chars[i + 1])) {
wordEnd = i;
// 开始反转
for (; wordStart < wordEnd;) {
char temp = chars[wordStart];
chars[wordStart] = chars[wordEnd];
chars[wordEnd] = temp;
wordStart++;
wordEnd--;
}
wordStart = 0;
wordEnd = 0;
}
lastChar = chars[i];
}
return new String(chars);
}
}